{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Profitable Schemes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: profitableSchemes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #盈利计划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>集团里有 <code>n</code> 名员工，他们可以完成各种各样的工作创造利润。</p>\n",
    "\n",
    "<p>第 <code>i</code> 种工作会产生 <code>profit[i]</code> 的利润，它要求 <code>group[i]</code> 名成员共同参与。如果成员参与了其中一项工作，就不能参与另一项工作。</p>\n",
    "\n",
    "<p>工作的任何至少产生 <code>minProfit</code> 利润的子集称为 <strong>盈利计划</strong> 。并且工作的成员总数最多为 <code>n</code> 。</p>\n",
    "\n",
    "<p>有多少种计划可以选择？因为答案很大，所以<strong> 返回结果模 </strong><code>10^9 + 7</code><strong> 的值</strong>。</p>\n",
    "\n",
    "<div class=\"original__bRMd\">\n",
    "<div>\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 5, minProfit = 3, group = [2,2], profit = [2,3]\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>至少产生 3 的利润，该集团可以完成工作 0 和工作 1 ，或仅完成工作 1 。\n",
    "总的来说，有两种计划。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 10, minProfit = 5, group = [2,3,5], profit = [6,7,8]\n",
    "<strong>输出：</strong>7\n",
    "<strong>解释：</strong>至少产生 5 的利润，只要完成其中一种工作就行，所以该集团可以完成任何工作。\n",
    "有 7 种可能的计划：(0)，(1)，(2)，(0,1)，(0,2)，(1,2)，以及 (0,1,2) 。</pre>\n",
    "</div>\n",
    "</div>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= n <= 100</code></li>\n",
    "\t<li><code>0 <= minProfit <= 100</code></li>\n",
    "\t<li><code>1 <= group.length <= 100</code></li>\n",
    "\t<li><code>1 <= group[i] <= 100</code></li>\n",
    "\t<li><code>profit.length == group.length</code></li>\n",
    "\t<li><code>0 <= profit[i] <= 100</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [profitable-schemes](https://leetcode.cn/problems/profitable-schemes/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [profitable-schemes](https://leetcode.cn/problems/profitable-schemes/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['5\\n3\\n[2,2]\\n[2,3]', '10\\n5\\n[2,3,5]\\n[6,7,8]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def profitableSchemes(self, n: int, minProfit: int, group: List[int], profit: List[int]) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "\n",
    "        # dp[i][j] 表示i个人完成工作能产生j利润的方案数\n",
    "        dp = [[0] * (minProfit + 1) for _ in range(n + 1)]\n",
    "        dp[0][0] = 1\n",
    "\n",
    "        for g, p in zip(group, profit):\n",
    "            # 从n个人开始，倒序考虑，避免重复计算\n",
    "            for i in range(n, g - 1, -1):\n",
    "                # 从当前利润开始，倒序考虑\n",
    "                for j in range(minProfit, -1, -1):\n",
    "                    dp[i][j] = (dp[i][j] + dp[i - g][max(0, j - p)]) % MOD\n",
    "\n",
    "        # 最后，求总的方案数\n",
    "        return sum(dp[i][minProfit] for i in range(n + 1)) % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef profitableSchemes(self, n, minProfit, group, profit):\n",
    "\t\tbase = 10 ** 9 + 7\n",
    "\t\tl = len(group)\n",
    "\t\tdp = {(0,0): 1}\n",
    "\t\tfor i in range(l):\n",
    "\t\t\ttmp = {}\n",
    "\t\t\tfor g, p in dp:\n",
    "\t\t\t\tif g + group[i] <= n:\n",
    "\t\t\t\t\tkey = (g + group[i], p + profit[i])\n",
    "\t\t\t\t\ttmp[key] = dp[(g,p)]\n",
    "\t\t\tfor key in tmp:\n",
    "\t\t\t\tdp[key] = (dp.get(key, 0) + tmp[key]) % base\n",
    "\t\tans = 0\n",
    "\t\tfor key in dp:\n",
    "\t\t\tif key[1] >= minProfit:\n",
    "\t\t\t\tans = (ans + dp[key]) % base\n",
    "\t\treturn ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def profitableSchemes(self, n: int, minProfit: int, group: List[int], profit: List[int]) -> int:\n",
    "        mod = int(1e9) + 7\n",
    "        njob = len(group)\n",
    "        from numpy import zeros\n",
    "        dp = zeros((2, minProfit + 1, n + 1))\n",
    "        cur = 0\n",
    "        for remp in range(0, minProfit + 1):\n",
    "            for reml in range(0, n + 1):\n",
    "                if remp > 0 and remp <= profit[-1] and reml >= group[-1]:\n",
    "                    dp[cur, remp, reml] = 1\n",
    "                elif remp == 0:\n",
    "                    if reml < group[-1]:\n",
    "                        dp[cur, remp, reml] = 1\n",
    "                    else:\n",
    "                        dp[cur, remp, reml] = 2\n",
    "        \n",
    "        cur = 1 - cur\n",
    "        for i in reversed(range(njob - 1)):\n",
    "            for remp in range(0, minProfit + 1):\n",
    "                for reml in range(0, n + 1):\n",
    "                    dp[cur, remp, reml] = ((dp[1 - cur, max(remp - profit[i], 0), reml - group[i]] if reml >= group[i] else 0) \\\n",
    "                        + dp[1 - cur, remp, reml]) % mod\n",
    "            cur = 1 - cur\n",
    "        return int(dp[1 - cur, minProfit, n])\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#盈利计划，输入：n = 5, minProfit = 3, group = [2,2], profit = [2,3]输出：2；输入：n = 10, minProfit = 5, group = [2,3,5], profit = [6,7,8]，输出：7\n",
    "#dp[i][j][k]表示前i个工作中选择j名员工，利润至少为k的盈利的总数目\n",
    "class Solution:\n",
    "    def profitableSchemes(self, n: int, minProfit: int, group: List[int], profit: List[int]) -> int:\n",
    "        len1,mod=len(group),10**9+7\n",
    "        dp=[[[0]*(minProfit+1) for i in range(n+1)] for j in range(len1+1)]\n",
    "        dp[0][0][0]=1#初始状态\n",
    "        for i in range(1,len1+1):#遍历物品\n",
    "            people,earn=group[i-1],profit[i-1]\n",
    "            for j in range(n+1):\n",
    "                for k in range(minProfit+1):#最后遍历容量\n",
    "                    if j<people:dp[i][j][k]=dp[i-1][j][k]\n",
    "                    else:\n",
    "                        dp[i][j][k]=(dp[i-1][j][k]+dp[i-1][j-people][max(0,k-earn)])%mod \n",
    "        total=sum(dp[len1][j][minProfit]for j in range(n+1))\n",
    "        return total%mod "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def profitableSchemes(self, n: int, minProfit: int, group: List[int], profit: List[int]) -> int:\r\n",
    "        Mod=10**9+7\r\n",
    "        l=len(group)\r\n",
    "        f=[[[0]*(minProfit+1) for _ in range(n+1)] for _ in range(l+1)]\r\n",
    "        for i in range(n+1):\r\n",
    "            f[0][i][0]=1\r\n",
    "        \r\n",
    "        for i in range(1,l+1):\r\n",
    "            for j in range(n+1):\r\n",
    "                for k in range(minProfit+1):\r\n",
    "                    f[i][j][k]=f[i-1][j][k]\r\n",
    "                    if j>=group[i-1]:\r\n",
    "                        f[i][j][k]+=f[i-1][j-group[i-1]][max(0,k-profit[i-1])]\r\n",
    "                    f[i][j][k]%=Mod\r\n",
    "        return f[-1][-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def profitableSchemes(self, n: int, minProfit: int, group: List[int], profit: List[int]) -> int:\n",
    "        m = len(group)\n",
    "        all_profit = sum(profit)\n",
    "        dp = [[[0 for _ in range(n+1)] for _ in range(minProfit+1)] for _ in range(m+1)]\n",
    "        \n",
    "        for k in range(n+1):\n",
    "            dp[0][0][k] = 1\n",
    "\n",
    "        for i in range(1, m+1):\n",
    "            for j in range(minProfit+1):\n",
    "                for k in range(n+1):\n",
    "                    dp[i][j][k] += dp[i-1][j][k]\n",
    "                    if k >= group[i-1]:\n",
    "                        if profit[i-1] > j:\n",
    "                            dp[i][j][k] += dp[i-1][0][k-group[i-1]]\n",
    "                        else:\n",
    "                            dp[i][j][k] += dp[i-1][j-profit[i-1]][k-group[i-1]]\n",
    "\n",
    "        return dp[m][minProfit][n] % (10**9+7)\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "\n",
    "SEED = 10 ** 9 + 7\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def profitableSchemes(self, n: int, minProfit: int, group: List[int], profit: List[int]) -> int:\n",
    "        dp_table = defaultdict(lambda: defaultdict(lambda: defaultdict(int)))\n",
    "        dp_table[0][0][0] = 1\n",
    "        if group[0] <= n:\n",
    "            dp_table[0][group[0]][min(profit[0], minProfit)] = 1\n",
    "\n",
    "        for ptr in range(1, len(profit)):\n",
    "            required_peoples = group[ptr]\n",
    "            gain_profit = profit[ptr]\n",
    "            for used_peoples in dp_table[ptr - 1].keys():\n",
    "                for possible_profits, cnt in dp_table[ptr - 1][used_peoples].items():\n",
    "                    dp_table[ptr][used_peoples][possible_profits] = (dp_table[ptr][used_peoples][possible_profits] + cnt) % SEED\n",
    "\n",
    "                    if used_peoples + required_peoples <= n:\n",
    "                        new_used_peoples = min(used_peoples + required_peoples, n)\n",
    "                        new_possible_profits = min(possible_profits + gain_profit, minProfit)\n",
    "                        dp_table[ptr][new_used_peoples][new_possible_profits] = (dp_table[ptr][new_used_peoples][new_possible_profits] + cnt) % SEED\n",
    "        \n",
    "        total = 0\n",
    "        for used_peoples in dp_table[len(profit) - 1].keys():\n",
    "            for possible_profits, cnt in dp_table[len(profit) - 1][used_peoples].items():\n",
    "                if possible_profits >= minProfit:\n",
    "                    total = (total + cnt) % SEED\n",
    "\n",
    "        # for ptr in dp_table.keys():\n",
    "        #     print(f\"ptr={ptr}\")\n",
    "        #     for used_peoples in dp_table[ptr].keys():\n",
    "        #         for possible_profits, cnt in dp_table[ptr][used_peoples].items():\n",
    "        #             print(f\"used_peoples={used_peoples} possible_profits={possible_profits}\") \n",
    "        #     print()\n",
    "\n",
    "        return total\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def profitableSchemes(self, n: int, minProfit: int, group: List[int], profit: List[int]) -> int:\n",
    "        tmp = list(zip(group, profit))\n",
    "        tmp.sort(key=lambda x: x[0])\n",
    "        group = [g for g, p in tmp]\n",
    "        profit = [p for g, p in tmp]\n",
    "\n",
    "        dp = [[collections.defaultdict(int) for _ in range(len(group)+1)] for _ in range(n+1)]\n",
    "        for i in range(n+1): dp[i][0][0] = 1\n",
    "        for j in range(len(group)+1): dp[0][j][0] = 1\n",
    "        ans = 0\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(1, len(group)+1):\n",
    "                if group[j-1]<=i:\n",
    "                    for p in dp[i-group[j-1]][j-1]:\n",
    "                        dp[i][j][min(minProfit, p+profit[j-1])] += dp[i-group[j-1]][j-1][p]\n",
    "                for p in dp[i][j-1]:\n",
    "                    dp[i][j][p] += dp[i][j-1][p]\n",
    "        return dp[-1][-1][minProfit]%(10**9+7)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def profitableSchemes(self, n: int, minProfit: int, group: List[int], profit: List[int]) -> int:\n",
    "        mode = 1000000007\n",
    "        zipped = zip(group,profit)\n",
    "        sort_zipped = sorted(zipped,key=lambda x:(x[0]), reverse=False)\n",
    "        result = zip(*sort_zipped)\n",
    "        group, profit = [list(x) for x in result]\n",
    "        record = [[{} for j in range(n+1)] for i in range(len(group))]\n",
    "        def dfs(idx:int, leavePerson:int, curProfit:int) -> int:\n",
    "            if idx >= len(group) or leavePerson < group[idx]:\n",
    "                return 0\n",
    "            if min(curProfit, minProfit) in record[idx][leavePerson]:\n",
    "                 return record[idx][leavePerson][min(curProfit, minProfit)]\n",
    "            timeNum = 0\n",
    "            timeNum += dfs(idx+1, leavePerson, curProfit)\n",
    "            timeNum += dfs(idx+1, leavePerson-group[idx], curProfit+profit[idx])\n",
    "            if curProfit+profit[idx] >= minProfit:\n",
    "                timeNum += 1\n",
    "            modeNum = timeNum%mode\n",
    "            record[idx][leavePerson][min(curProfit, minProfit)] = modeNum\n",
    "            return modeNum\n",
    "        return dfs(0, n, 0) + (1 if minProfit == 0 else 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def profitableSchemes(self, n: int, minProfit: int, group: List[int], profit: List[int]) -> int:\n",
    "        mod = 10**9+7\n",
    "        nums = sorted([[x,y] for x,y in zip(group,profit)])\n",
    "        @cache\n",
    "        def back(cur,x,v):\n",
    "            if v >= minProfit:v = inf\n",
    "            if cur == len(nums) or x-nums[cur][0] < 0:return 1 if v >= minProfit else 0\n",
    "            return (back(cur+1,x-nums[cur][0],v+nums[cur][1])+back(cur+1,x,v))%mod\n",
    "        res = back(0,n,0)\n",
    "        del back\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def profitableSchemes(self, G: int, P: int, group: List[int], profit: List[int]) -> int:\n",
    "        n = len(group)\n",
    "        q = [-1]*n\n",
    "        for i in range(0,n):\n",
    "            q[i] = [-1]*(G+1)\n",
    "            for j in range(0,G+1):\n",
    "                q[i][j] = [-1]*(P+1)\n",
    "        def maxnum(i,num,mon):\n",
    "            if( num >= G or i>=n):\n",
    "                if( mon >= P):\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0\n",
    "            if( q[i][num][mon] != -1):\n",
    "                return q[i][num][mon]\n",
    "            if( num + group[i] > G):\n",
    "                q[i][num][mon] = maxnum(i+1,num,mon)\n",
    "            else:\n",
    "                q[i][num][mon] =( maxnum(i+1,num+group[i], min(mon+profit[i],P) ) + maxnum(i+1,num,mon) )\n",
    "            return q[i][num][mon]%(10**9+7)\n",
    "                \n",
    "        return maxnum(0,0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def profitableSchemes(self, G: int, P: int, group: List[int], profit: List[int]) -> int:\n",
    "        n = len(profit)\n",
    "        dp = [[[-1] * (G+1) for _ in range(P+1)] for _ in range(n+1)]\n",
    "\n",
    "        def fun(g, p, i):\n",
    "            if i == -1:\n",
    "                if p >= P:\n",
    "                    return 1\n",
    "                return 0\n",
    "\n",
    "            g = min(g, G)\n",
    "            p = min(p, P)\n",
    "\n",
    "            if dp[i][p][g] != -1:\n",
    "                return dp[i][p][g]\n",
    "\n",
    "            ans = 0\n",
    "            if (group[i] + g) <= G:\n",
    "                t = fun(group[i] + g, p + profit[i], i - 1)\n",
    "                ans += t\n",
    "            t= fun(g, p, i - 1)\n",
    "            ans += t\n",
    "            dp[i][p][g] = ans\n",
    "            return ans\n",
    "\n",
    "        MOD = 10 ** 9 + 7  \n",
    "        ans = fun(0, 0, n-1)\n",
    "        # print(dp)\n",
    "        return ans % MOD\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def profitableSchemes(self, n: int, minProfit: int, group: List[int], profit: List[int]) -> int:\n",
    "        m=len(group)\n",
    "        A=list(zip(group,profit))\n",
    "        A.sort()\n",
    "        @lru_cache(None)\n",
    "        def dfs(i,P,N):\n",
    "            if i==m:\n",
    "                return not P\n",
    "            g,p=A[i]\n",
    "            if g>N:\n",
    "                return not P\n",
    "            else:\n",
    "                if P==minProfit:\n",
    "                    return sum(dfs(i+1,j,N-g) for j in range(max(minProfit-p,0),minProfit+1)) + dfs(i+1,minProfit,N)\n",
    "                elif P>=p:\n",
    "                    return dfs(i+1,P-p,N-g)+dfs(i+1,P,N)\n",
    "                else:\n",
    "                    return dfs(i+1,P,N)\n",
    "        return int(dfs(0,minProfit,n))%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def profitableSchemes(self, n: int, minProfit: int, group: List[int], profit: List[int]) -> int:\n",
    "        m=len(group)\n",
    "        A=list(zip(group,profit))\n",
    "        A.sort()\n",
    "        @lru_cache(None)\n",
    "        def dfs(i,P,N):\n",
    "            if i==m:\n",
    "                return not P\n",
    "            g,p=A[i]\n",
    "            if P==minProfit:\n",
    "                if g<=N:\n",
    "                    return sum(dfs(i+1,j,N-g) for j in range(max(minProfit-p,0),minProfit+1)) + dfs(i+1,minProfit,N)\n",
    "                else:\n",
    "                    return dfs(i+1,minProfit,N)\n",
    "            elif P>=p:\n",
    "                if g<=N:\n",
    "                    return dfs(i+1,P-p,N-g)+dfs(i+1,P,N)\n",
    "                else:\n",
    "                    return dfs(i+1,P,N)\n",
    "            else:\n",
    "                return dfs(i+1,P,N)\n",
    "        return int(dfs(0,minProfit,n))%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def profitableSchemes(self, n: int, minProfit: int, group: List[int], profit: List[int]) -> int:\n",
    "        @cache\n",
    "        def dfs(i, j, k):\n",
    "            # 从i开始选，当前已选员工数量，当前利润\n",
    "            if i >= len(group):\n",
    "                return 1 if k == minProfit else 0\n",
    "            ans = dfs(i + 1, j, k)\n",
    "            if j + group[i] <= n:\n",
    "                ans += dfs(i + 1, j + group[i], min(k + profit[i], minProfit))\n",
    "            return ans % mod\n",
    "\n",
    "\n",
    "        mod = 10**9 + 7\n",
    "        m = len(group)\n",
    "        ans = dfs(0, 0, 0)\n",
    "        dfs.cache_clear()\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def profitableSchemes(self, n: int, minProfit: int, group: List[int], profit: List[int]) -> int:\n",
    "        m = len(group)\n",
    "        @cache\n",
    "        def p(i, rest, prof):\n",
    "            if rest < 0:\n",
    "                return 0\n",
    "            if i == m:\n",
    "                return 1 if prof >= minProfit else 0\n",
    "            res = p(i+1, rest, prof) + p(i+1, rest-group[i], min(prof+profit[i], minProfit))\n",
    "            return res\n",
    "        res = p(0, n, 0) % int(1e9+7)\n",
    "        p.cache_clear()\n",
    "        return res\n",
    "            \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def profitableSchemes(self, n: int, minProfit: int, group: List[int], profit: List[int]) -> int:\n",
    "        self.table = {}\n",
    "        return self.cal(n, minProfit, group, profit, 0, {}) % int(1e9 + 7)\n",
    "    \n",
    "    def cal(self, n, minProfit, group, profit, i, table):\n",
    "        if (n, minProfit, i) not in table:\n",
    "            m = len(profit)\n",
    "            if i == m:\n",
    "                if minProfit <= 0:\n",
    "                    table[(n, minProfit, i)] = 1\n",
    "                else:\n",
    "                    table[(n, minProfit, i)] = 0\n",
    "            else:\n",
    "                if minProfit >= 0:\n",
    "                    res = 0\n",
    "                    if group[i] <= n:\n",
    "                        res += self.cal(n - group[i], minProfit - profit[i], group, profit, i + 1, table)\n",
    "                    res += self.cal(n, minProfit, group, profit, i + 1, table)\n",
    "                    table[(n, minProfit, i)] = res\n",
    "                else:\n",
    "                    table[(n, minProfit, i)] = self.cal2(n, group, i)\n",
    "        return table[(n, minProfit, i)]\n",
    "\n",
    "    def cal2(self, n, group, i):\n",
    "        if (n, i) not in self.table:\n",
    "            if i == len(group):\n",
    "                self.table[(n, i)] = 1\n",
    "            else:\n",
    "                res = 0\n",
    "                if group[i] <= n:\n",
    "                    res += self.cal2(n - group[i], group, i + 1)\n",
    "                res += self.cal2(n, group, i + 1)\n",
    "                self.table[(n, i)] = res\n",
    "        return self.table[(n, i)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def profitableSchemes(self, n: int, minProfit: int, group: List[int], profit: List[int]) -> int:\n",
    "        dp = defaultdict(int)\n",
    "        dp[(0, 0, 0)] = 1\n",
    "        for i in range(len(group)):\n",
    "            for j in range(n + 1):\n",
    "                for k in range(minProfit + 1):\n",
    "                    if j >= group[i]:\n",
    "                        dp[(i + 1, j, k)] =  dp[(i, j - group[i], max(0, k - profit[i]))]\n",
    "                    dp[(i + 1, j, k)] += dp[(i, j, k)]\n",
    "        \n",
    "        ret = 0\n",
    "        for j in range(n + 1):\n",
    "            ret += dp[(len(group), j, minProfit)]\n",
    "        \n",
    "        return ret % (10 **  9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def profitableSchemes(self, n: int, minProfit: int, group: List[int], profit: List[int]) -> int:\n",
    "        m = len(profit)\n",
    "        maxProfit = sum(profit)\n",
    "\n",
    "        # dp[i][g][p]\n",
    "        dp = [[{} for _ in range(n+1)] for _ in range(m+1)]\n",
    "        dp[0][0][0] = 1\n",
    "        for i in range(m):\n",
    "            for g in range(n+1):\n",
    "                for p, s in dp[i][g].items():\n",
    "                    if p in dp[i+1][g]:\n",
    "                        dp[i+1][g][p] += s\n",
    "                    else:\n",
    "                        dp[i+1][g][p] = s\n",
    "                    if g + group[i] <= n:\n",
    "                        if p + profit[i] in dp[i+1][g + group[i]]:\n",
    "                            dp[i+1][g + group[i]][p + profit[i]] += s\n",
    "                        else:\n",
    "                            dp[i+1][g + group[i]][p + profit[i]] = s\n",
    "        \n",
    "        # print(dp)\n",
    "        ans = 0\n",
    "        for g in range(n+1):\n",
    "            for p, s in dp[m][g].items():\n",
    "                if p >= minProfit:\n",
    "                    ans += s\n",
    "\n",
    "        return ans%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def profitableSchemes(self, n: int, minProfit: int, group: List[int], profit: List[int]) -> int:\n",
    "        m = len(group)\n",
    "        dp = [[Counter() for _ in range(n + 1)] for _ in range(m)]\n",
    "\n",
    "        for i in range(n + 1):\n",
    "            dp[0][i][0] = 1\n",
    "            if group[0] <= i:\n",
    "                dp[0][i][profit[0]] = 1\n",
    "\n",
    "        for i, (person_num, profit_num) in enumerate(zip(group[1:], profit[1:]), 1):\n",
    "            for j in range(n + 1):\n",
    "                for key, times in dp[i - 1][j].items():\n",
    "                    dp[i][j][key] += times\n",
    "                if j - person_num >= 0:\n",
    "                    for key, times in dp[i - 1][j - person_num].items():\n",
    "                        dp[i][j][key + profit_num] += times\n",
    "        mask = 10 ** 9 + 7\n",
    "        ans = 0\n",
    "        for num, times in dp[m - 1][n].items():\n",
    "            if num >= minProfit:\n",
    "                ans = (ans % mask + times % mask) % mask\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def profitableSchemes(self, n: int, minProfit: int, group: List[int], profit: List[int]) -> int:\n",
    "        m = len(group)\n",
    "        prs1 = [0]\n",
    "        for pro in profit:\n",
    "            if prs1:\n",
    "                prs1.append(prs1[-1]+pro)\n",
    "            else:\n",
    "                prs1.append(pro)\n",
    "        n = min(n,sum(group))\n",
    "        if prs1[-1] < minProfit:\n",
    "            return 0\n",
    "        dp=[[{} for _ in range(n+1)] for _ in range(m+1)]\n",
    "        pro=profit[0]\n",
    "        for j in range(n+1):\n",
    "            dp[0][j][0] = 1\n",
    "        for i in range(1,m+1):\n",
    "            k2=prs1[i]+1\n",
    "            for j in range(0,n+1):\n",
    "                j3=j-group[i-1]\n",
    "                for k in dp[i-1][j]:\n",
    "                    dp[i][j][k]=dp[i-1][j][k]\n",
    "                if j3 >= 0:\n",
    "                    for k3 in dp[i-1][j3]:\n",
    "                        k=k3+profit[i-1]\n",
    "                        dp2=dp[i-1][j3][k3]\n",
    "                        if k in dp[i][j]:\n",
    "                            dp[i][j][k]+=dp2\n",
    "                        else:\n",
    "                            dp[i][j][k]=dp2\n",
    "        ans=0\n",
    "        for k in dp[-1][-1]:\n",
    "            if k>=minProfit:\n",
    "                ans+=dp[-1][-1][k]\n",
    "        return ans % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, people_num, profit):\n",
    "        self.people_num = people_num\n",
    "        self.profit = profit\n",
    "    def __lt__(self, b):\n",
    "        if self.profit != b.profit:\n",
    "            return self.profit > b.profit\n",
    "        return self.people_num < b.people_num\n",
    "\n",
    "class Solution:\n",
    "    def profitableSchemes(self, n: int, minProfit: int, group: List[int], profit: List[int]) -> int:\n",
    "        \n",
    "        group_num = len(group)\n",
    "        a = []\n",
    "        for people_num, profit_i in zip(group, profit):\n",
    "            a.append(Node(people_num, profit_i))\n",
    "        \n",
    "        a.sort()\n",
    "        #print(a)\n",
    "\n",
    "        need_people_sum = [0] * (len(profit)+1)\n",
    "\n",
    "        for i, node in enumerate(a):\n",
    "            group[i], profit[i] = node.people_num, node.profit\n",
    "            need_people_sum[i+1] = need_people_sum[i] + group[i]    \n",
    "        \n",
    "        #for i in range(len(group)):\n",
    "        #    need_people_sum[i+1] = need_people_sum[i] + group[i]\n",
    "\n",
    "\n",
    "        cnt = 0\n",
    "        mp = {}\n",
    "        ans = 0\n",
    "       \n",
    "        def dfs(cur, rest_people, prefix):\n",
    "            nonlocal n, minProfit, cnt, ans\n",
    "\n",
    "            prefix = min(prefix, minProfit)\n",
    "            key = (cur, rest_people, prefix)\n",
    "            \n",
    "            \n",
    "            if key in mp:\n",
    "                return mp[key]\n",
    "           \n",
    "            if prefix >= minProfit and rest_people >= need_people_sum[-1] - need_people_sum[cur]:\n",
    "                mp[key] = 2 ** (group_num - cur)\n",
    "                return mp[key]\n",
    "\n",
    "            elif prefix < minProfit and cur < n and sum(profit[cur:]) < minProfit - prefix:\n",
    "                mp[key] = 0\n",
    "                return 0\n",
    "\n",
    "            if cur == group_num:\n",
    "                if prefix >= minProfit:\n",
    "                    cnt +=1\n",
    "                mp[key] = 1 * (prefix >= minProfit)\n",
    "                return prefix >= minProfit\n",
    "\n",
    "            else:\n",
    "                tmp = 0\n",
    "                if rest_people >= group[cur]:\n",
    "                    tmp = dfs(cur+1, rest_people - group[cur], prefix + profit[cur])\n",
    "\n",
    "                tmp += dfs(cur+1, rest_people, prefix ) \n",
    "                mp[key] = tmp \n",
    "                ans = max(ans, tmp) \n",
    "                return mp[key]\n",
    "        \n",
    "        dfs(0, n, 0)\n",
    "\n",
    "        return ans  % (10 **9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, people_num, profit):\n",
    "        self.people_num = people_num\n",
    "        self.profit = profit\n",
    "    def __lt__(self, b):\n",
    "        if self.profit != b.profit:\n",
    "            return self.profit > b.profit\n",
    "        return self.people_num < b.people_num\n",
    "\n",
    "class Solution:\n",
    "    def profitableSchemes(self, n: int, minProfit: int, group: List[int], profit: List[int]) -> int:\n",
    "        \n",
    "        group_num = len(group)\n",
    "        a = []\n",
    "        for people_num, profit_i in zip(group, profit):\n",
    "            a.append(Node(people_num, profit_i))\n",
    "        \n",
    "        a.sort()\n",
    "        #print(a)\n",
    "\n",
    "        need_people_sum = [0] * (len(profit)+1)\n",
    "\n",
    "        for i, node in enumerate(a):\n",
    "            group[i], profit[i] = node.people_num, node.profit\n",
    "            need_people_sum[i+1] = need_people_sum[i] + group[i]    \n",
    "        \n",
    "        #for i in range(len(group)):\n",
    "        #    need_people_sum[i+1] = need_people_sum[i] + group[i]\n",
    "\n",
    "\n",
    "        cnt = 0\n",
    "        mp = {}\n",
    "        ans = 0\n",
    "       \n",
    "        def dfs(cur, rest_people, prefix):\n",
    "            nonlocal n, minProfit, cnt, ans\n",
    "\n",
    "            prefix = min(prefix, minProfit) # 如果超过最小收益要求，置为 minProfit\n",
    "            key = (cur, rest_people, prefix)\n",
    "            \n",
    "            \n",
    "            if key in mp:\n",
    "                return mp[key]\n",
    "           \n",
    "            if prefix >= minProfit and rest_people >= need_people_sum[-1] - need_people_sum[cur]:\n",
    "                mp[key] = 2 ** (group_num - cur)\n",
    "                return mp[key]\n",
    "\n",
    "            elif prefix < minProfit and cur < n and sum(profit[cur:]) < minProfit - prefix:\n",
    "                mp[key] = 0\n",
    "                return 0\n",
    "\n",
    "            if cur == group_num:\n",
    "                if prefix >= minProfit:\n",
    "                    cnt +=1\n",
    "                mp[key] = 1 * (prefix >= minProfit)\n",
    "                return prefix >= minProfit\n",
    "\n",
    "            else:\n",
    "                tmp = 0\n",
    "                if rest_people >= group[cur]:\n",
    "                    tmp = dfs(cur+1, rest_people - group[cur], prefix + profit[cur])\n",
    "\n",
    "                tmp += dfs(cur+1, rest_people, prefix ) \n",
    "                mp[key] = tmp \n",
    "                ans = max(ans, tmp) \n",
    "                return mp[key]\n",
    "        \n",
    "        dfs(0, n, 0)\n",
    "\n",
    "        return ans  % (10 **9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def profitableSchemes(self, n: int, minProfit: int, group: List[int], profit: List[int]) -> int:\n",
    "        res=0\n",
    "        ans=0\n",
    "        N=len(group)\n",
    "        dp1=[[[-1]*(1+minProfit) for _ in range(n+2)] for _ in range(N)] \n",
    "        dp=[[-1]*(n+2) for _ in range(N)]\n",
    "        @cache   \n",
    "        def dfs1(i,j,k):\n",
    "            nonlocal ans,N\n",
    "            \n",
    "            if j<0 or k<0: \n",
    "                #dp1[i][j][k]=0\n",
    "                return 0\n",
    "            if i==-1: \n",
    "                #dp1[i][j][k]=0\n",
    "                return 0 \n",
    "            if dp1[i][j][k]>-1: return dp1[i][j][k]\n",
    "            if i==0:\n",
    "                if j==0 and k==0: \n",
    "                    if N==1: ans+=1\n",
    "                    dp1[i][j][k]=1 \n",
    "                    return 1\n",
    "                elif j==group[i] and k==profit[i]: \n",
    "                    if N==1: ans+=1\n",
    "                    dp1[i][j][k]=1\n",
    "                    return 1 \n",
    "                else: \n",
    "                    dp1[i][j][k]=0\n",
    "                    return 0\n",
    "            \n",
    "            a = dfs1(i-1,j-group[i],k-profit[i])+dfs1(i-1,j,k)\n",
    "            if i==N-1: ans+=a\n",
    "            dp1[i][j][k]=a  \n",
    "            return a\n",
    "        \n",
    "        @cache   \n",
    "        def dfs(i,j):\n",
    "\n",
    "            nonlocal res,N  \n",
    "            \n",
    "            if j<0: \n",
    "                #dp[i][j]=0\n",
    "                return 0\n",
    "            if i==-1:\n",
    "                #dp[i][j]=0 \n",
    "                return 0 \n",
    "            if dp[i][j]>-1: return dp[i][j]\n",
    "            if i==0:\n",
    "                if j==0: \n",
    "                    if N==1: res+=1\n",
    "                    dp[i][j]=1\n",
    "                    return 1\n",
    "                elif j==group[i]: \n",
    "                    if N==1: res+=1\n",
    "                    dp[i][j]=1\n",
    "                    return 1 \n",
    "                else: \n",
    "                    dp[i][j]=1\n",
    "                    return 0\n",
    "            \n",
    "            a = dfs(i-1,j-group[i])+dfs(i-1,j)\n",
    "            if i==N-1: res+=a\n",
    "            dp[i][j]=a\n",
    "            return a\n",
    "        \n",
    "        for i in range(n+1):\n",
    "            dfs(N-1,i)\n",
    "        for i in range(n+1):\n",
    "            for j in range(minProfit):\n",
    "                dfs1(N-1,i,j)  \n",
    "        #print(res,ans) \n",
    "        return (res-ans)%(10**9+7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def profitableSchemes(self, n: int, minProfit: int, group: List[int], profit: List[int]) -> int:\n",
    "        from functools import lru_cache\n",
    "        ls = list(zip(group, profit))\n",
    "        mod = int(1e9) + 7\n",
    "        ls.sort(reverse=True)\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dp(idx, member, pp):\n",
    "            if idx == len(ls):\n",
    "                return 1 if pp <= 0 else 0\n",
    "            xx, v = ls[idx]\n",
    "            if member >= xx:\n",
    "                return (dp(idx + 1, member, pp) + dp(idx + 1, member - xx, pp - v)) % mod\n",
    "            else:\n",
    "                return dp(idx + 1, member, pp) % mod\n",
    "\n",
    "        ans = dp(0, n, minProfit)\n",
    "        dp.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def profitableSchemes(self, n: int, minProfit: int, group: List[int], profit: List[int]) -> int:\n",
    "        gAndP = [(g, p) for g, p in zip(group, profit)]\n",
    "        gAndP.sort(reverse=True)\n",
    "        N = len(group)\n",
    "        planCache = {}\n",
    "        limitLessCache = {}\n",
    "        def limitLess(peopleRemain, off):\n",
    "            g = gAndP[off][0]\n",
    "            if peopleRemain < g: return 0\n",
    "            if off == 0: return 1\n",
    "            key = (peopleRemain, off)\n",
    "            cached = limitLessCache.get(key)\n",
    "            if cached is not None: return cached\n",
    "            limitLessCache[key]= cached = limitLess(peopleRemain, off-1) + limitLess(peopleRemain-g, off-1) + 1\n",
    "            return cached\n",
    "\n",
    "        def plans(peopleRemain, minProfit, off):\n",
    "            g, p = gAndP[off]\n",
    "            if peopleRemain < g: return 0\n",
    "            if minProfit <= 0:\n",
    "                return limitLess(peopleRemain, off)\n",
    "            if off == 0: return int(p >= minProfit)\n",
    "            key = (peopleRemain, minProfit, off)\n",
    "            cached = planCache.get(key)\n",
    "            if cached is not None: return cached\n",
    "            planCache[key] = cached = plans(peopleRemain, minProfit, off-1) + plans(peopleRemain - g, minProfit - p, off - 1) + (minProfit<=p)\n",
    "            return cached           \n",
    "        result = plans(n, minProfit, N - 1) % 1000000007 + (minProfit <= 0)\n",
    "        # print(gAndP, planCache, limitLessCache)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from typing import List, Any\n",
    "from functools import lru_cache, cache\n",
    "from itertools import combinations\n",
    "import sys\n",
    "\n",
    "sys.setrecursionlimit(999)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def profitableSchemes(self, n: int, minProfit: int, group: List[int], profit: List[int]) -> int:\n",
    "        \"\"\"\n",
    "\n",
    "        :param n:\n",
    "        :param minProfit:\n",
    "        :param group:\n",
    "        :param profit:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "\n",
    "        @cache\n",
    "        def get_ans(cur_idx, cur_n, cur_profit):\n",
    "            if cur_idx == len(self.ll) or cur_n < self.ll[cur_idx][0]:\n",
    "                if cur_profit == self.min_profit:\n",
    "                    return 1\n",
    "                return 0\n",
    "            a = get_ans(cur_idx + 1, cur_n, cur_profit) % (10 ** 9 + 7)\n",
    "            b =  get_ans(cur_idx + 1, cur_n - self.ll[cur_idx][0],\n",
    "                             min(self.min_profit, cur_profit + self.ll[cur_idx][1])) % (10 ** 9 + 7)\n",
    "            return (a + b) % (10 ** 9 + 7)\n",
    "\n",
    "        self.n = n\n",
    "        self.min_profit = minProfit\n",
    "        ll = [i for i in zip(group, profit)]\n",
    "        ll.sort(key=lambda x: (x[0], -x[1]))\n",
    "        self.ll = ll\n",
    "        ans = get_ans(0, n, 0)\n",
    "        return ans % (10 ** 9 + 7)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from typing import List, Any\n",
    "from functools import lru_cache, cache\n",
    "from itertools import combinations\n",
    "import sys\n",
    "\n",
    "sys.setrecursionlimit(999)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def profitableSchemes(self, n: int, minProfit: int, group: List[int], profit: List[int]) -> int:\n",
    "        \"\"\"\n",
    "\n",
    "        :param n:\n",
    "        :param minProfit:\n",
    "        :param group:\n",
    "        :param profit:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        ll = [i for i in zip(group, profit)]\n",
    "        ll.sort(key=lambda x: (x[0]))\n",
    "        @lru_cache(None)\n",
    "        def get_ans(cur_idx, cur_n, cur_profit):\n",
    "            if cur_idx == len(ll) or cur_n < ll[cur_idx][0]:\n",
    "                if cur_profit >= minProfit:\n",
    "                    return 1\n",
    "                return 0\n",
    "            return (get_ans(cur_idx + 1, cur_n, cur_profit) + get_ans(cur_idx + 1, cur_n - ll[cur_idx][0],\n",
    "                             min(minProfit, cur_profit + ll[cur_idx][1])) ) % (10 ** 9 + 7)\n",
    "\n",
    "        ans = get_ans(0, n, 0)\n",
    "        return ans % (10 ** 9 + 7)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def profitableSchemes(self, n: int, minProfit: int, group: List[int], profit: List[int]) -> int:\n",
    "        l = len(group)\n",
    "        t = sorted([[group[i], profit[i]] for i in range(l)])#按照group升序\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, c, s):#分别是项目索引，所剩人数，利润总和\n",
    "            if i == l or t[i][0] > c:#如果已经遍历完所有项目或者所剩任务不能完成任何一个后续项目\n",
    "                return 1 if s == minProfit else 0#如果利润达到要求，返回1，否则返回0\n",
    "            #01背包，做i项目或者不做的和，限制最大利润上限也是优化点\n",
    "            return (dfs(i + 1, c, s) + dfs(i + 1, c - t[i][0], min(minProfit, s + t[i][1]))) % mod\n",
    "        mod = 10 ** 9 + 7\n",
    "        return dfs(0, n, 0)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, people_num, profit):\n",
    "        self.people_num = people_num\n",
    "        self.profit = profit\n",
    "    def __lt__(self, b):\n",
    "        if self.profit != b.profit:\n",
    "            return self.profit > b.profit\n",
    "        return self.people_num < b.people_num\n",
    "\n",
    "class Solution:\n",
    "    def profitableSchemes(self, n: int, minProfit: int, group: List[int], profit: List[int]) -> int:\n",
    "        \n",
    "        group_num = len(group)\n",
    "        a = []\n",
    "        for people_num, profit_i in zip(group, profit):\n",
    "            a.append(Node(people_num, profit_i))\n",
    "        \n",
    "        a.sort()\n",
    "        #print(a)\n",
    "\n",
    "        need_people_sum = [0] * (len(profit)+1)\n",
    "\n",
    "        for i, node in enumerate(a):\n",
    "            group[i], profit[i] = node.people_num, node.profit\n",
    "            need_people_sum[i+1] = need_people_sum[i] + group[i]    \n",
    "        \n",
    "        #for i in range(len(group)):\n",
    "        #    need_people_sum[i+1] = need_people_sum[i] + group[i]\n",
    "\n",
    "\n",
    "        cnt = 0\n",
    "        mp = {}\n",
    "        ans = 0\n",
    "       \n",
    "        def dfs(cur, rest_people, prefix):\n",
    "            nonlocal n, minProfit, cnt, ans\n",
    "\n",
    "            prefix = min(prefix, minProfit) # 如果超过最小收益要求，置为 minProfit\n",
    "            key = (cur, rest_people, prefix)\n",
    "            \n",
    "            \n",
    "            if key in mp:\n",
    "                return mp[key]\n",
    "           \n",
    "\n",
    "            if cur == group_num:\n",
    "                if prefix >= minProfit:\n",
    "                    cnt +=1\n",
    "                mp[key] = 1 * (prefix >= minProfit)\n",
    "                return prefix >= minProfit\n",
    "\n",
    "            else:\n",
    "                tmp = 0\n",
    "                if rest_people >= group[cur]:\n",
    "                    tmp = dfs(cur+1, rest_people - group[cur], prefix + profit[cur])\n",
    "\n",
    "                tmp += dfs(cur+1, rest_people, prefix ) \n",
    "                mp[key] = tmp \n",
    "                ans = max(ans, tmp) \n",
    "                return mp[key]\n",
    "        \n",
    "        dfs(0, n, 0)\n",
    "\n",
    "        return ans  % (10 **9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def profitableSchemes(self, n: int, minProfit: int, group: List[int], profit: List[int]) -> int:\n",
    "        mode = 1000000007\n",
    "        zipped = zip(group,profit)\n",
    "        sort_zipped = sorted(zipped,key=lambda x:(x[0]), reverse=False)\n",
    "        result = zip(*sort_zipped)\n",
    "        group, profit = [list(x) for x in result]\n",
    "        record = [[{} for j in range(n+1)] for i in range(len(group))]\n",
    "        @lru_cache(None)\n",
    "        def dfs(idx:int, leavePerson:int, curProfit:int) -> int:\n",
    "            if idx >= len(group) or leavePerson < group[idx]:\n",
    "                return 0\n",
    "            if curProfit >= minProfit:\n",
    "                curProfit = minProfit\n",
    "            timeNum = 0\n",
    "            timeNum += dfs(idx+1, leavePerson, curProfit)\n",
    "            if leavePerson >= group[idx]:\n",
    "                timeNum += dfs(idx+1, leavePerson-group[idx], curProfit+profit[idx])\n",
    "                if curProfit+profit[idx] >= minProfit:\n",
    "                    timeNum += 1\n",
    "            modeNum = timeNum%mode\n",
    "            return modeNum\n",
    "        return dfs(0, n, 0) + (1 if minProfit == 0 else 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def profitableSchemes(self, n: int, minProfit: int, group: List[int], profit: List[int]) -> int:\n",
    "        nums = sorted([(a,b) for a,b in zip(group,profit)])\n",
    "        MOD = 10**9+7\n",
    "        @cache\n",
    "        def dfs(i,cur_people,cur_profit):\n",
    "            if cur_profit > minProfit:\n",
    "                cur_profit = inf\n",
    "            if i == len(group) or cur_people - nums[i][0] < 0:\n",
    "                return int(cur_profit>=minProfit)\n",
    "            \n",
    "            return  (dfs(i+1,cur_people-nums[i][0], cur_profit+nums[i][1]) + dfs(i+1, cur_people, cur_profit))%MOD\n",
    "        \n",
    "        return dfs(0,n,0)\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def profitableSchemes(self, n: int, minProfit: int, group: List[int], profit: List[int]) -> int:\n",
    "        @lru_cache(None)\n",
    "        def help(i, n, p):\n",
    "            if n < 0:\n",
    "                return 0\n",
    "            if i == len(A):\n",
    "                return int(p==0)\n",
    "            return help(i+1, n, p) + help(i+1, n-A[i][0], max(0, p-A[i][1]))\n",
    "        A = sorted(zip(group, profit))\n",
    "        return help(0, n, minProfit) % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def profitableSchemes(self, n: int, minProfit: int, group: List[int], profit: List[int]) -> int:\n",
    "        @lru_cache(None)\n",
    "        def help(i, n, p):\n",
    "            if n < 0:\n",
    "                return 0\n",
    "            if i == len(A):\n",
    "                return int(p==0)\n",
    "            return help(i+1, n, p) + help(i+1, n-A[i][0], max(0, p-A[i][1]))\n",
    "        A = sorted(zip(group, profit), reverse=True)\n",
    "        return help(0, n, minProfit) % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from typing import List, Any\n",
    "from functools import lru_cache, cache\n",
    "from itertools import combinations\n",
    "import sys\n",
    "\n",
    "sys.setrecursionlimit(999)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def profitableSchemes(self, n: int, minProfit: int, group: List[int], profit: List[int]) -> int:\n",
    "        \"\"\"\n",
    "\n",
    "        :param n:\n",
    "        :param minProfit:\n",
    "        :param group:\n",
    "        :param profit:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        self.n = n\n",
    "        self.min_profit = minProfit\n",
    "        ll = [i for i in zip(group, profit)]\n",
    "        ll.sort(key=lambda x: (x[0], -x[1]))\n",
    "        self.ll = ll\n",
    "        ans = self.get_ans(0, n, 0)\n",
    "        return ans % (10 ** 9 + 7)\n",
    "\n",
    "    @cache\n",
    "    def get_ans(self, cur_idx, cur_n, cur_profit):\n",
    "        if cur_idx == len(self.ll) or cur_n < self.ll[cur_idx][0]:\n",
    "            if cur_profit == self.min_profit:\n",
    "                return 1\n",
    "            return 0\n",
    "        a = self.get_ans(cur_idx + 1, cur_n, cur_profit) % (10 ** 9 + 7) \n",
    "        b = self.get_ans(cur_idx + 1, cur_n - self.ll[cur_idx][0], min(self.min_profit, cur_profit + self.ll[cur_idx][1]) ) % (10 ** 9 + 7)\n",
    "        return (a + b) % (10 ** 9 + 7)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "class Solution:\n",
    "    def profitableSchemes(self, G: int, P: int, group: List[int], profit: List[int]) -> int:\n",
    "        val = [(g, p) for g, p in zip(group, profit)]\n",
    "        val.sort(key = lambda x : x[0], reverse=True)\n",
    "\n",
    "        # 背包大小为n，选前k种物品，总收益大于等于p的方法数\n",
    "        @lru_cache(typed=False, maxsize=12800000000)\n",
    "        def dp(n, k, p):\n",
    "            if p > 0 and n < val[k][0]:\n",
    "                return 0\n",
    "\n",
    "            if n == 0:\n",
    "                return 1 if p == 0 else 0\n",
    "\n",
    "            if k == 0:\n",
    "                ans = 0\n",
    "                if p == 0:\n",
    "                    ans += 1\n",
    "                if n >= val[0][0] and val[0][1] >= p:\n",
    "                    ans += 1\n",
    "            \n",
    "            else:\n",
    "                ans = dp(n, k-1, p)\n",
    "                if n >= val[k][0]:\n",
    "                    ans += dp(n-val[k][0], k-1, max(0, p - val[k][1]))\n",
    "            return ans % 1000000007\n",
    "        return dp(G, len(group)-1, P)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    from functools import lru_cache\n",
    "    def profitableSchemes(self, n: int, minProfit: int, group: List[int], profit: List[int]) -> int:\n",
    "        M = 10**9 + 7\n",
    "        num = len(group)\n",
    "        dp = [[0]*(n + 1) for _ in range(num + 1)]\n",
    "        for i in range(1,num + 1):\n",
    "            for j in range(n + 1):\n",
    "                if group[i - 1] <= j:\n",
    "                    dp[i][j] = max(dp[i - 1][j],dp[i - 1][j - group[i - 1]]+profit[i - 1])\n",
    "                else:\n",
    "                    dp[i][j] = dp[i - 1][j]\n",
    "        @lru_cache(None)\n",
    "        def find(pre:int,worker:int):\n",
    "            if pre == -1:\n",
    "                return 1\n",
    "            worker_n = group[pre]\n",
    "            if worker_n <= worker:\n",
    "                return find(pre - 1,worker - worker_n) + find(pre - 1,worker)\n",
    "            else:\n",
    "                return find(pre - 1,worker)\n",
    "        @lru_cache(None)\n",
    "        def solve(pre:int,worker:int,target:int):\n",
    "            if target <= 0:\n",
    "                return find(pre,worker)\n",
    "            if dp[pre + 1][worker] < target:\n",
    "                return 0\n",
    "            now_worker = group[pre]\n",
    "            now_v = profit[pre]\n",
    "            t1 = solve(pre - 1,worker,target)\n",
    "            if now_worker > worker:\n",
    "                return t1\n",
    "            else:\n",
    "                if now_v < target:\n",
    "                    return t1 + solve(pre - 1,worker - group[pre],target - profit[pre])\n",
    "                else:\n",
    "                    return t1 + solve(pre - 1,worker - group[pre],0)\n",
    "        return solve(num - 1,n,minProfit) % M"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def profitableSchemes(self, n: int, minProfit: int, group: List[int], profit: List[int]) -> int:\n",
    "        @lru_cache(None)\n",
    "        def help1(i, n, p):\n",
    "            if n < 0 or p <= 0:\n",
    "                return 0\n",
    "            if i == len(A):\n",
    "                return 1\n",
    "            return help1(i + 1, n, p) + help1(i + 1, n -A[i][0], p - A[i][1])\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def help2(i, n):\n",
    "            if n < 0:\n",
    "                return 0\n",
    "            if i == len(A):\n",
    "                return 1\n",
    "            return help2(i+1, n) + help2(i+1,n-A[i][0])\n",
    "\n",
    "        A = sorted(zip(group, profit), reverse=True)\n",
    "        return (help2(0, n) - help1(0, n, minProfit)) % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def profitableSchemes(self, n: int, minProfit: int, group: List[int], profit: List[int]) -> int:\n",
    "        mod = 10**9+7\n",
    "        # accumulate 可能不支持\n",
    "        pres = list(accumulate(profit, initial=0))\n",
    "        pre_group = list(accumulate(group, initial=0))\n",
    "        def query(pres, i, j):\n",
    "            # 闭区间 [i, j] 的和\n",
    "            return pres[j+1] - pres[i]\n",
    "        inf = float('inf')\n",
    "        # @cache\n",
    "        @lru_cache(None)\n",
    "        def h(left, i, minProfit):\n",
    "            if left<0: return 0 # 人不够\n",
    "            # 利润肯定不够，提前结束\n",
    "            if query(pres, i, len(group)-1)<minProfit: return 0\n",
    "            if i==len(group): return int(minProfit<=0) # 利润是否达标\n",
    "            # 是否完成当前工作\n",
    "            res = h(left, i+1, minProfit)\n",
    "            if left>=group[i]:\n",
    "                # left 一定充足的话，改成inf, 减少状态\n",
    "                if left>=query(pre_group, i, len(group)-1):\n",
    "                    left = inf\n",
    "                else:\n",
    "                    left -= group[i]\n",
    "                # 利润已经够了，改成 0，减少状态\n",
    "                res += h(left, i+1, max(minProfit-profit[i], 0))\n",
    "            return res%mod\n",
    "            \n",
    "        return h(n, 0, minProfit)%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def profitableSchemes(self, n: int, minProfit: int, group: List[int], profit: List[int]) -> int:\n",
    "        N = len(group)\n",
    "        # dp: people*leftProfit\n",
    "        MOD = 10**9 + 7\n",
    "        @cache\n",
    "        def dfs(i,workers,limitProfit):\n",
    "            if i ==N or workers<=0:\n",
    "                return 0\n",
    "            ret = dfs(i+1,workers,limitProfit)\n",
    "            if group[i]<=workers:\n",
    "                nextProfit = max(0,limitProfit-profit[i])\n",
    "                if nextProfit == 0:\n",
    "                    ret+=1\n",
    "                ret = (dfs(i+1,workers-group[i],nextProfit)+ret)%MOD\n",
    "            return ret \n",
    "        return dfs(0,n,minProfit) + (1 if minProfit==0 else 0)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def profitableSchemes(self, n: int, minProfit: int, group: List[int], profit: List[int]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        m = len(group)\n",
    "        @cache\n",
    "        def dfs(i, re_people, pro):\n",
    "            if re_people <= 0:\n",
    "                return 1 if pro == 0 else 0\n",
    "            if i < 0:\n",
    "                return 1 if pro == 0 else 0\n",
    "            #不选\n",
    "            res1 = dfs(i - 1, re_people, pro)\n",
    "            res2 = 0\n",
    "            #选\n",
    "            if re_people >= group[i]:\n",
    "                res2 = dfs(i - 1, re_people - group[i], max(0, pro - profit[i]))\n",
    "            return (res1 + res2) % MOD\n",
    "        return dfs(m - 1, n, minProfit)\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def profitableSchemes(self, n: int, minProfit: int, group: List[int], profit: List[int]) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        @cache\n",
    "        def helper(rest_src, p, index):\n",
    "            if index == len(group):\n",
    "                return int(p == minProfit)\n",
    "            if 0 <= rest_src < group[index]:\n",
    "                return helper(rest_src, p, index + 1)\n",
    "            if presum[-1] - presum[index] < rest_src:\n",
    "                rest_src = float(\"inf\")\n",
    "            return helper(rest_src - group[index], min(p + profit[index], minProfit), index+1) + helper(rest_src, p, index+1)\n",
    "        presum = list(accumulate(group, initial=0))\n",
    "        return helper(n, 0, 0) % mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def profitableSchemes(self, n: int, minProfit: int, group: List[int], profit: List[int]) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        m = len(group)\n",
    "        @lru_cache(None)\n",
    "        def dfs(i,x,y):\n",
    "            if i == m or x == 0:return int(y >= minProfit)\n",
    "            ans = dfs(i+1,x,y)\n",
    "            if x >= group[i]:\n",
    "                ans += dfs(i+1,x-group[i],min(minProfit,y+profit[i]))\n",
    "            return ans\n",
    "\n",
    "        return dfs(0,n,0) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def profitableSchemes(self, nn: int, minProfit: int, group: List[int], profit: List[int]) -> int:\n",
    "        \n",
    "        @cache \n",
    "        def f(i, n, p):\n",
    "            if i == group.__len__():\n",
    "                if p == 0:\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0\n",
    "         \n",
    "            s = 0 \n",
    "            if n >= group[i]:\n",
    "                s += f(i+1, n-group[i], max(0,p-profit[i]))\n",
    "                s += f(i+1, n, p)\n",
    "            else:\n",
    "                s += f(i+1, n, p)\n",
    "            return s \n",
    "        ans = f(0, nn, minProfit)\n",
    "        return ans % (10**9+7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def profitableSchemes(self, n: int, minProfit: int, group: List[int], profit: List[int]) -> int:\n",
    "        # 记忆化搜索\n",
    "        @cache\n",
    "        def dfs(i,n,k):\n",
    "            if n < 0:\n",
    "                return 0\n",
    "            if i == len(group):\n",
    "                return int(k==0)\n",
    "            return (dfs(i+1,n,k) + dfs(i+1,n-group[i],max(0,k-profit[i])))%(10**9+7)\n",
    "        return dfs(0,n,minProfit)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def profitableSchemes(self, n: int, minProfit: int, group: List[int], profit: List[int]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        m = len(group)\n",
    "        @cache\n",
    "        def dfs(i, re_people, pro):\n",
    "            nonlocal minProfit\n",
    "            if re_people <= 0:\n",
    "                return 1 if pro >= minProfit else 0\n",
    "            if i < 0:\n",
    "                return 1 if pro >= minProfit else 0\n",
    "            #不选\n",
    "            res1 = dfs(i - 1, re_people, pro)\n",
    "            res2 = 0\n",
    "            #选\n",
    "            if re_people >= group[i]:\n",
    "                res2 = dfs(i - 1, re_people - group[i], min(101, pro + profit[i]))\n",
    "            return (res1 + res2) % MOD\n",
    "        return dfs(m - 1, n, 0)\n",
    "\n",
    "            "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
